package com.itheima.datastructure.demo1;
/**
 * 柠檬水找零问题的解决方案
 *
 * 该类提供了一个方法来判断是否能够为每个顾客正确找零
 * 顾客可能会用5美元、10美元或20美元的钞票支付柠檬水费用（每杯5美元）
 * 收银员初始时没有零钱可以找给顾客
 * 该问题的核心是判断在任意时刻收银员是否有足够的5美元和10美元钞票来找零
 */
public class lemonChange {

    /**
     * 程序的入口点
     *
     * @param args 命令行参数，不用于本问题
     */
    public static void main(String[] args) {
        // 测试change方法的一个示例
        System.out.println(change(new int[]{5,5,20}));
    }

    /**
     * 检查是否能够为每个顾客正确找零
     *
     * @param bills 顾客支付的钞票数组，其中只包含5、10和20三个整数
     * @return boolean 如果能够为每个顾客正确找零，则返回true；否则返回false
     */
    public static boolean change(int[] bills) {
        // 初始化5美元和10美元钞票的数量
        int five = 0, ten = 0;

        // 遍历顾客支付的每一张钞票
        for (int bill : bills) {
            if (bill == 5) {
                // 如果顾客支付了5美元，增加5美元钞票的数量
                five++;
            } else if (bill == 10) {
                // 如果顾客支付了10美元，需要找零5美元
                if (five == 0) {
                    // 如果没有5美元钞票，无法找零，返回false
                    return false;
                }
                // 找零5美元后，增加10美元钞票的数量
                five--;
                ten++;
            } else {
                // 如果顾客支付了20美元，优先使用10美元和5美元找零，或者使用三张5美元找零
                if (ten > 0 && five > 0) {
                    // 使用一张10美元和一张5美元找零
                    five--;
                    ten--;
                } else if (five >= 3) {
                    // 如果没有10美元，使用三张5美元找零
                    five -= 3;
                } else {
                    // 无法找零，返回false
                    return false;
                }
            }
        }

        // 所有顾客都能找零，返回true
        return true;
    }
}
